//矩阵区域和
//测试链接 https://leetcode.cn/problems/matrix-block-sum/
public class MatrixBlockSum {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length;
        int n = mat[0].length;

        int[][] dp = new int[m+1][n+1];

        for(int x = 1; x <= m; x++){
            for(int y = 1; y <= n; y++){
                //计算二维前缀和
                dp[x][y] = dp[x][y-1] + dp[x-1][y] - dp[x-1][y-1] + mat[x-1][y-1];
            }
        }

        int[][] ret = new int[m][n];
        for(int x = 0; x < m; x++){
            for(int y = 0; y < n; y++){
                int x1 = Math.max(0,x-k) + 1;
                int y1 = Math.max(0,y-k) + 1;

                int x2 = Math.min(m-1,x+k) + 1;
                int y2 = Math.min(n-1,y+k) + 1;

                //计算（x1,y1）和 （x2,y2）之间构成的矩阵和
                ret[x][y] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
            }
        }

        return ret;

    }
}
